404. 左叶子之和

#leetcode/tree/traversal

404. 左叶子之和

Similar Question

leading to the advanced question

Solution Tips

方案一: BFS

var sumOfLeftLeaves = function(root) {
    if (root === null) return 0;
    let sum = 0;
    const queue = [{ node: root, side: 'right' }];
    
    while (queue.length !== 0) {
        const { node, side } = queue.pop();
        if (node.left === null && node.right === null && side === 'left') {
            sum += node.val;
        }
        if (node.left !== null) {
            queue.push({
                node: node.left,
                side: 'left'
            });
        }
        if (node.right !== null) {
            queue.push({
                node: node.right,
                side: 'right'
            });
        }
    }

    return sum;
};

方案二: DFS

var sumOfLeftLeaves = function(root) {
    if (root === null) return 0;
    return (
        sumOfLeftLeaves(root.left)
        + sumOfLeftLeaves(root.right)
        + (root.left !== null && root.left.left === null && root.left.right === null ? root.left.val : 0)
    );
};